Company-Interview-Problem/Problems/Hashing/Longest Subarray with Sum K.cpp at main · trex-ayush/Company-Interview-Problem · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
/*
    Problem Name: Geeksforgeeks Longest Subarray with Sum K
    https://www.geeksforgeeks.org/problems/longest-sub-array-with-sum-k0809/1
    Company : Amazon (1+ year ago)
*/

/*
    Time Complexity : O(n)
    Space Complexity : O(n)
*/
class Solution {
  public:
    int longestSubarray(vector<int>& arr, int k) {
        int n = arr.size();
        int maxLen = 0;
        unordered_map<int,int> mpp;  // { sum , index }
        int sum = 0;
        int j = 0;

        while(j < n){
            sum += arr[j];

            if(sum == k){
                maxLen = max(maxLen , j + 1);
            }

            int target = sum - k;
            if(mpp.find(target) != mpp.end()){
                maxLen = max(maxLen , j - mpp[target]);
            }
            if(mpp.find(sum) == mpp.end()){
                mpp[sum] = j;
            }
            j++;
        }
        return maxLen;
    }
};